package com.cdream.basic.algorithm.leetcode.stack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author cdream
 * @date 2022/3/23
 */
public class Question496 {
    public static void main(String[] args) {
        new Question496().nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2});
    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] res = new int[n];
        Arrays.fill(res,-1);
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i<n; i++){
            map.put(nums1[i],i);
        }

        LinkedList<Integer> stack = new LinkedList<>();
        for(int i = 0 ;i <nums2.length; i++){
            while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
                int k = stack.poll();
                Integer n1 = map.get(k);
                if(n1!=null){
                    res[n1] = nums2[i];
                }
            }
            stack.push(i);
        }
        return res;

    }
}
